from collections import Counter,defaultdict

"""思路：
1.滑动窗口：
我们可以使用滑动窗口从左到右遍历字符串，确保窗口的子串长度满足条件。
2.记录不同字母：
使用一个字典（或者集合）来跟踪滑动窗口中出现的不同字母，并确保其数量不超过 maxLetters。
3.计数子串出现次数：
使用一个哈希表（字典）来存储子串的出现次数。
4.优化窗口长度：
因为我们只关心长度大于等于 minSize 且小于等于 maxSize 的子串，而更大的长度需要更多计算。
考虑到一个子串的扩展会包含更短的子串（如果条件满足），我们可以仅考虑长度为 minSize 的子串以减少计算。
5.返回结果：
遍历完字符串后，从字典中找到出现次数最多的子串。
"""
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        # 用于记录子串出现的次数
        has = defaultdict(int)
        # 当前窗口的字符计数
        cnt = Counter()
        # 当前窗口中不同字符的数量
        unique_count = 0
        ans = 0
        left = 0
        for right in range(n):
            c = s[right]
            cnt[c] += 1
            if cnt[c] == 1:
                unique_count += 1

            # 如果窗口长度大于 minsize,缩小窗口
            if right - left + 1 > minSize:
                cnt[s[left]] -= 1
                if cnt[s[left]] == 0:
                    unique_count -= 1
                left += 1

            # 窗口长度为minsize时，检查条件
            if right - left + 1 == minSize and unique_count <= maxLetters:
                sub = s[left:right + 1]
                has[sub] += 1
                ans = max(ans, has[sub])
        return ans
